package sort;

/**
 * 快速排序算法实现类
 */
public class QuickSort {
    
    /**
     * 使用快速排序算法对整型数组进行排序
     * @param arr 待排序的整型数组
     */
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSortHelper(arr, 0, arr.length - 1);
    }
    
    /**
     * 快速排序递归辅助方法
     * @param arr 待排序的数组
     * @param low 起始索引
     * @param high 结束索引
     */
    private static void quickSortHelper(int[] arr, int low, int high) {
        if (low < high) {
            // 获取分区点
            int pivotIndex = partition(arr, low, high);
            
            // 递归排序分区点左侧的元素
            quickSortHelper(arr, low, pivotIndex - 1);
            
            // 递归排序分区点右侧的元素
            quickSortHelper(arr, pivotIndex + 1, high);
        }
    }
    
    /**
     * 分区方法，将数组分为两部分
     * @param arr 数组
     * @param low 起始索引
     * @param high 结束索引
     * @return 分区点索引
     */
    private static int partition(int[] arr, int low, int high) {
        // 选择最后一个元素作为基准点
        int pivot = arr[high];
        
        // 小于基准点的元素的索引
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            // 如果当前元素小于或等于基准点
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        // 将基准点放到正确位置
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    /**
     * 交换数组中两个元素的位置
     * @param arr 数组
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    /**
     * 打印数组元素
     * @param arr 要打印的数组
     */
    public static void printArray(int[] arr) {
        if (arr == null) {
            System.out.println("数组为空");
            return;
        }
        
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}